home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2002 #3 / Amiga Plus CD - 2002 - No. 03.iso / AmigaPlus / Tools / Development / renderlib40 / src / rnd_quant.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-12-21  |  8.4 KB  |  379 lines
  1.  
  2. #include <math.h>
  3. #include "lib_init.h"
  4. #include "lib_debug.h"
  5. #include <render/render.h>
  6. #include <proto/utility.h>
  7. #include <proto/exec.h>
  8.  
  9. /*
  10. **    quantization tree node
  11. */
  12.  
  13. struct quantizenode
  14. {
  15.     struct quantizenode *left, *right;            /* child nodes */
  16.     struct RNDHistoEntry **lower, **upper;        /* range */
  17.     ULONG numentries;    /* number of entries represented by this node */
  18.     ULONG min, max;        /* min max values of this component */
  19.     FLOAT diversity;    /* separation criterium */
  20.     FLOAT cc_mid[3];    /* average color represented by this node */
  21.     ULONG shift, mask;
  22. };
  23.  
  24.  
  25. /*-------------------------------------------------------------------
  26.  
  27.     quantizenode = CreateNode(memhandler, lower, upper)
  28.     create a new quantization node for the given field.
  29.  
  30. -------------------------------------------------------------------*/
  31.  
  32. static struct quantizenode *CreateNode(RNDMH *rmh, struct RNDHistoEntry **lower, struct RNDHistoEntry **upper)
  33. {
  34.     struct quantizenode *qn = AllocRenderMem(rmh, sizeof(struct quantizenode));
  35.     if (qn)
  36.     {
  37.         FLOAT diversity[3];
  38.         FLOAT a;
  39.         LONG c1, c2, c3;
  40.         LONG min[3];
  41.         LONG max[3];
  42.         FLOAT numpixel = 0;
  43.         struct RNDHistoEntry **htp;
  44.         FLOAT maxd;
  45.         ULONG shift, mask;
  46.         ULONG component;
  47.  
  48.         qn->cc_mid[0] = 0;
  49.         qn->cc_mid[1] = 0;
  50.         qn->cc_mid[2] = 0;
  51.     
  52.         qn->left = NULL;
  53.         qn->right = NULL;
  54.         qn->lower = lower;
  55.         qn->upper = upper;
  56.         qn->numentries = upper - lower + 1;
  57.  
  58.         diversity[0] = 0;
  59.         diversity[1] = 0;
  60.         diversity[2] = 0;
  61.         
  62.         min[0] = 256;
  63.         min[1] = 256;
  64.         min[2] = 256;
  65.  
  66.         max[0] = -1;
  67.         max[1] = -1;
  68.         max[2] = -1;
  69.  
  70.         htp = lower;
  71.         while (htp <= upper)
  72.         {
  73.             ULONG rgb = (*htp)->rgb;
  74.             ULONG count = (*htp)->count;
  75.             c1 = (rgb & 0xff0000) >> 16;
  76.             c2 = (rgb & 0x00ff00) >> 8;
  77.             c3 = rgb & 0x0000ff;
  78.             
  79.             if (c1 < min[0]) min[0] = c1;
  80.             if (c1 > max[0]) max[0] = c1;
  81.             if (c2 < min[1]) min[1] = c2;
  82.             if (c2 > max[1]) max[1] = c2;
  83.             if (c3 < min[2]) min[2] = c3;
  84.             if (c3 > max[2]) max[2] = c3;
  85.  
  86.             qn->cc_mid[0] += (FLOAT) c1 * count;
  87.             qn->cc_mid[1] += (FLOAT) c2 * count;
  88.             qn->cc_mid[2] += (FLOAT) c3 * count;
  89.  
  90.             htp++;
  91.             numpixel += count;
  92.         }
  93.         
  94.         qn->cc_mid[0] /= numpixel;
  95.         qn->cc_mid[1] /= numpixel;
  96.         qn->cc_mid[2] /= numpixel;
  97.  
  98.         htp = lower;
  99.         while (htp <= upper)
  100.         {
  101.             ULONG rgb = (*htp)->rgb;
  102.             c1 = (rgb & 0xff0000) >> 16;
  103.             c2 = (rgb & 0x00ff00) >> 8;
  104.             c3 = rgb & 0x0000ff;
  105.             
  106.             c1 -= qn->cc_mid[0];
  107.             c2 -= qn->cc_mid[1];
  108.             c3 -= qn->cc_mid[2];
  109.  
  110.         /*    a = sqrt((DOUBLE) (*htp)->count);    */
  111.             a = pow((DOUBLE) (*htp)->count, 0.35);
  112.  
  113.             diversity[0] += (FLOAT) (c1 * c1) * a;
  114.             diversity[1] += (FLOAT) (c2 * c2) * a;
  115.             diversity[2] += (FLOAT) (c3 * c3) * a;
  116.             htp++;
  117.         }
  118.  
  119.         maxd = diversity[0]; component = 0; mask = 0xff0000; shift = 16;
  120.         if (diversity[1] > maxd) { maxd = diversity[1]; component = 1; mask = 0x00ff00; shift = 8; }
  121.         if (diversity[2] > maxd) { maxd = diversity[2]; component = 2; mask = 0x0000ff; shift = 0; }
  122.         qn->diversity = maxd;
  123.         qn->shift = shift;
  124.         qn->mask = mask;
  125.         qn->min = min[component];
  126.         qn->max = max[component];
  127.     }
  128.  
  129.     return qn;
  130. }
  131.  
  132.  
  133. /*-------------------------------------------------------------------
  134.  
  135.     cutindex = Separate(quantizenode)
  136.  
  137.     separate a node's array and return the cut index.
  138.     (cutindex := new upper node's lower index)
  139.     
  140. -------------------------------------------------------------------*/
  141.  
  142. static ULONG Separate(struct quantizenode *node)
  143. {
  144.     struct RNDHistoEntry **lentry = node->lower;
  145.     struct RNDHistoEntry **uentry = node->upper;
  146.     struct RNDHistoEntry *temp;
  147.     
  148.     ULONG mid = node->min + (node->max - node->min) / 2;
  149.     ULONG cutindex = 0;
  150.  
  151.     while (lentry < uentry)
  152.     {
  153.         if ((((*lentry)->rgb & node->mask) >> node->shift) > mid)
  154.         {
  155.             while ((((*uentry)->rgb & node->mask) >> node->shift) > mid) uentry--;
  156.             temp = *lentry;
  157.             *lentry = *uentry;
  158.             *uentry = temp;
  159.             uentry--;
  160.         }        
  161.         lentry++;
  162.         cutindex++;
  163.     }
  164.  
  165.     return cutindex;
  166. }
  167.  
  168.  
  169. /*-------------------------------------------------------------------
  170.  
  171.     FreeTree(node)
  172.     free tree
  173.  
  174. -------------------------------------------------------------------*/
  175.  
  176. static void FreeTree(RNDMH *rmh, struct quantizenode *node)
  177. {
  178.     if (node->left) FreeTree(rmh, node->left);
  179.     if (node->right) FreeTree(rmh, node->right);
  180.     FreeRenderMem(rmh, node, sizeof(struct quantizenode));
  181. }
  182.  
  183.  
  184. /*-------------------------------------------------------------------
  185.  
  186.     newtableptr = DecomposeTree(node, ctableptr)
  187.     decompose tree to colortable
  188.  
  189. -------------------------------------------------------------------*/
  190.  
  191. static ULONG *DecomposeTree(struct quantizenode *node, ULONG *tabentry)
  192. {
  193.     if (node->left && node->right)
  194.     {
  195.         tabentry = DecomposeTree(node->left, tabentry);
  196.         tabentry = DecomposeTree(node->right, tabentry);
  197.     }
  198.     else
  199.     {
  200.         ULONG rgb;
  201.         rgb = (ULONG) node->cc_mid[0];
  202.         rgb <<= 8;
  203.         rgb |= (ULONG) node->cc_mid[1];
  204.         rgb <<= 8;
  205.         rgb |= (ULONG) node->cc_mid[2];
  206.         *tabentry++ = rgb;
  207.     }
  208.     return tabentry;
  209. }
  210.  
  211.  
  212. /*-------------------------------------------------------------------
  213.  
  214.     dmaxnode = FindNode(node, dmaxnode)
  215.     recurse tree and find end node with diversity[max].
  216.     at initial call, dmaxnode must point to a dummy node
  217.     with node->diversity = 0
  218.  
  219. -------------------------------------------------------------------*/
  220.  
  221. static struct quantizenode *FindNode(struct quantizenode *node, struct quantizenode *dmaxnode)
  222. {
  223.     if (node->left && node->right)
  224.     {
  225.         dmaxnode = FindNode(node->left, dmaxnode);
  226.         dmaxnode = FindNode(node->right, dmaxnode);
  227.     }
  228.     else
  229.     {
  230.         if (node->diversity > dmaxnode->diversity)
  231.         {
  232.             dmaxnode = node;
  233.         }
  234.     }
  235.  
  236.     return dmaxnode;
  237. }
  238.  
  239.  
  240. /*-------------------------------------------------------------------
  241.  
  242.     result = Quantize(memhandler, histoptrarray, numhist, palptr, numcolors)
  243.     quantize main
  244.  
  245. -------------------------------------------------------------------*/
  246.  
  247. static ULONG Quantize(RNDMH *rmh, struct RNDHistoEntry **histoptrtab, ULONG numhist, ULONG *pptr, ULONG numcol, struct Hook *proghook, RNDHISTO *h)
  248. {
  249.     ULONG result = EXTP_NOT_ENOUGH_MEMORY;
  250.     struct quantizenode *rootnode;
  251.  
  252.     struct RND_ProgressMessage progmsg;
  253.     progmsg.RND_PMsg_type = PMSGTYPE_COLORS_CHOSEN;
  254.     progmsg.RND_PMsg_total = numcol;
  255.  
  256.     rootnode = CreateNode(rmh, histoptrtab, histoptrtab + numhist - 1);
  257.     if (rootnode)
  258.     {
  259.         struct quantizenode *maxdnode = rootnode, dummynode;
  260.         ULONG numnodes = 1, cutindex;
  261.     
  262.         dummynode.diversity = 0;
  263.         result = EXTP_SUCCESS;
  264.         
  265.         while (numnodes < numcol)
  266.         {
  267.             cutindex = Separate(maxdnode);
  268.     
  269.             maxdnode->left = CreateNode(rmh, maxdnode->lower, maxdnode->lower + cutindex - 1);
  270.             maxdnode->right = CreateNode(rmh, maxdnode->lower + cutindex, maxdnode->upper);
  271.             
  272.             if (proghook)
  273.             {
  274.                 progmsg.RND_PMsg_count = numnodes;
  275.                 if (!CallHookPkt(proghook, h, &progmsg))
  276.                 {
  277.                     result = EXTP_CALLBACK_ABORTED;
  278.                     goto abort;
  279.                 }
  280.             }
  281.     
  282.             if (maxdnode->left && maxdnode->right)
  283.             {
  284.                 maxdnode = FindNode(rootnode, &dummynode);
  285.                 numnodes++;
  286.                 continue;
  287.             }
  288.             
  289.             result = EXTP_NOT_ENOUGH_MEMORY;
  290.             break;
  291.         }
  292.         
  293.         if (result == EXTP_SUCCESS)
  294.         {
  295.             DecomposeTree(rootnode, pptr);
  296.         }
  297. abort:        
  298.         FreeTree(rmh, rootnode);
  299.     }
  300.  
  301.     return result;
  302. }
  303.  
  304.  
  305. /*****************************************************************************
  306. **
  307. **    extractpalette
  308. */
  309.  
  310. LIBAPI ULONG ExtractPaletteA(RNDHISTO *h, RNDPAL *p, UWORD numcol, struct TagItem *tags)
  311. {
  312.     RNDMH *rmh;
  313.     BOOL newpal;
  314.     ULONG firstcol;
  315.     ULONG result = EXTP_NO_DATA;
  316.     ULONG numhcol;
  317.     struct RNDHistoEntry **hparray;
  318.     struct Hook *proghook;
  319.     
  320.     if (!h || !p || !numcol) return result;
  321.  
  322.     proghook = (struct Hook *) GetTagData(RND_ProgressHook, NULL, tags);
  323.     rmh = (APTR) GetTagData(RND_RMHandler, (ULONG) h->rmh, tags);
  324.     newpal = (BOOL) GetTagData(RND_NewPalette, TRUE, tags);
  325.     firstcol = GetTagData(RND_FirstColor, 0, tags);
  326.     
  327.     ObtainSemaphoreShared(&h->lock);
  328.  
  329.     numhcol = QueryHistogram(h, RND_NumColors);
  330.     if (numhcol >= numcol)
  331.     {
  332.         hparray = CreateHistogramPointerArray(h);
  333.         if (hparray)
  334.         {
  335.             ULONG *pptr;
  336.             ObtainSemaphore(&p->lock);
  337.  
  338.             FlushPalette(p);
  339.     
  340.             if (newpal)
  341.             {
  342.                 p->numcolors = 0;
  343.                 memfill32(p->table, 256*4, 0);
  344.             }
  345.     
  346.             pptr = p->table + firstcol;
  347.     
  348.             if (numhcol == numcol)
  349.             {
  350.                 LONG i;
  351.                 for (i = 0; i < numcol; ++i)
  352.                 {
  353.                     *pptr++ = hparray[i]->rgb;
  354.                 }
  355.                 result = EXTP_SUCCESS;
  356.             }
  357.             else
  358.             {
  359.                 result = Quantize(rmh, hparray, numhcol, pptr, numcol, proghook, h);
  360.             }
  361.     
  362.             if (firstcol + numcol > p->numcolors)
  363.             {
  364.                 p->numcolors = firstcol + numcol;
  365.             }
  366.     
  367.             ReleaseSemaphore(&p->lock);
  368.             FreeRenderVec((ULONG *) hparray);
  369.         }
  370.         else
  371.         {
  372.             result = EXTP_NOT_ENOUGH_MEMORY;
  373.         }
  374.     }
  375.  
  376.     ReleaseSemaphore(&h->lock);
  377.     return result;
  378. }
  379.